[[분류:정보]]
==개요==
이 문서는 '쉽게 배우는 알고리즘'이라는 책에 기반하여 작성되었다.
어떤 항목들을 정렬하는 알고리즘으로, 매우 다양한 방법과 시간복잡도를 가진다. 배열뿐만 아니라 힙과 같은 트리 구조 등을 사용할 수 있다. 시간복잡도 문서는 [[시간 복잡도]] 문서 참고.
==기초적인 정렬 알고리즘==
===선택 정렬(Selection Sort)===
가장 작은(또는 큰) 원소를 찾아 맨 앞(또는 뒤)의 원소와 교환하는 과정을 반복하여 전체를 정렬하는 방식이다. 본 문서에서는 가장 큰 원소를 찾는 것을 기준으로 서술한다.
====의사 코드(간이화)====
선택 정렬의 의미를 간단히 서술한 코드이다.
{{{#!syntax java
selectionSort(A[], n):
for last ← n-1 downto 1
A[0…last] 중 가장 큰 수 A[k]를 찾는다.
A[k] ↔ A[last]
}}}
====의사 코드====
의사코드 1에서 큰 수를 찾고, 두 수를 교환하는 과정을 엄밀하게 서술한 코드이다.
{{{#!syntax java
selectionSort(A[], n):
for last ← n-1 downto 1
k ← theLargest(A, last)
tmp ← A[k]; A[k] ← A[last]; A[last] ← tmp
theLargest(A[], last):
largest ← 0
for i ← 1 to last
if (A[i] > A[largest])
largest ← i
return largest
}}}
====분석====
의사코드 1을 보자. 선택 정렬의 수행 시간은 모든 경우에 [math(\Theta(n^2))]이다. for 루프는 [math(n-1)]번 순환하고, index 교환은 상수 시간이 든다. 큰 수를 찾는 것은 작업은 부분 배열의 크기에 비례한다.[* 크기가 k인 배열에서 가장 큰 수를 찾는 데는 [math(k-1)]번의 비교가 필요하다.] 부분 배열의 크기는 for문에서 n부터 시작하여 2까지 감소한다. 그러므로 비교하는 총 횟수는 [math((n-1)+(n-2)+…+1=\dfrac{n(n-1)}{2})], 즉 [math(\Theta(n^2))]이다.
===버블 정렬(Bubble Sort)===
인접한 두 요소를 반복적으로 비교하고, 순서가 맞지 않으면 서로 자리를 바꾸는 방식으로 데이터를 정렬하는 알고리즘이다.
====의사 코드 (간이화)====
버블 정렬의 의미를 간단히 서술한 코드이다.
{{{#!syntax java
bubbleSort(A[], n):
for last ← n-1 downto 1
for i ← 0 to last-1
if (A[i] > A[i+1])
A[i] ↔ A[i+1]
}}}
====의사 코드====
이미 정렬이 완료된 상태이면 작업을 종료한다.
{{{#!syntax java
bubbleSort(A[], n):
sorted ← FALSE
for last ← n-1 downto 1
sorted ← TRUE
for i ← 0 to last-1
if (A[i] > A[i+1])
A[i] ↔ A[i+1]
sorted ← FALSE
if (sorted) return
}}}
====분석====
===삽입 정렬(Insertion Sort)===
이미 정렬된 부분 데이터에 새로운 데이터를 하나씩 비교하며 올바른 위치에 '삽입'하여 정렬을 완성하는 알고리즘이다.
====의사 코드 (간이화)====
삽입 정렬의 의미를 간단히 서술한 코드이다.
{{{#!syntax java
insertionSort(A[], n):
for i ← 1 to n-1
A[0…i]의 적합한 자리에 A[i]를 삽입한다.
}}}
====의사 코드 (재귀)====
{{{#!syntax java
insertionSort(A[], n):
if (n>1)
insertionSort(A[], n-1)
A[0…n-1]의 적합한 자리에 A[n-1]를 삽입한다.
}}}
====의사 코드 ====
적합한 자리를 찾는 로직을 풀어 서술한 코드이다.
{{{#!syntax java
insertionSort(A[], n):
for i ← 1 to n-1
newItem ← A[i]
for (j←i-1; 0 ≤ j and newItem < A[j]; j--)
A[j] ← A[j+1]
A[j+1] ← newItem
}}}
====분석====
==고급 정렬 알고리즘==
===병합 정렬(Merge Sort)===
===퀵 정렬(Quick Sort)===
===힙 정렬(Heap Sort)===
===셸 정렬(Shell Sort)===
